class Solution {
    public int cuttingRope(int n) {
        //当所有绳段长度相等时，乘积最大。最优的绳段长度为3 .
        //尽可能将绳子以长度 3等分为多段时，乘积最大。
        //最优：3.把绳子尽可能切为多个长度为3的片段，留下的最后一段绳子的长度可能为 0,1,2三种情况。
        //次优：2.若最后一段绳子长度为 222 ；则保留，不再拆为 1+1。
        //最差：1.若最后一段绳子长度为 111 ；则应把一份3+1替换为2+2，因为 2×2>3×12。
        if(n <= 3) {
            return n-1;
        }
        int yu = n % 3;
        int qu = 1000000007;
        int shang = n/3;
        long ret = 1;
        for(int i = 1;i < shang;i++ ){
            ret = 3*ret%qu;
        }
        if(yu == 0) {
            return (int)(ret*3%qu);
        }
        if(yu == 1) {
            return (int)(ret*4%qu);
        }
        return (int)(ret*6%qu);
    }
}